1. Field of the Invention
The present invention relates to virtual machines within computer systems. More specifically, the present invention relates to a method and an apparatus for determining the frequency of execution of compiled methods within a virtual machine.
2. Related Art
The Java 2 Platform, Micro Edition (J2ME™), has become very popular in the wireless device space. Motorola, Nokia, NTT DoCoMo, RIM, Siemens, and many other key players in the wireless device industry have recently started shipping J2ME-enabled devices in very high volume. It has been estimated that over 200 million J2ME-enabled mobile phones were shipped in 2003 alone.
One major limitation of these wireless devices is the relatively small amount of memory available for executing programs. Many methods have been developed to optimize memory usage in these memory-constrained devices. Once such method involves using a dynamic compiler that supports both the execution of interpreted code and compiled code. Code that is executed more often is compiled and executed in compiled mode, while code that is executed less often is executed in interpreted mode. Note that the compiled code executes much faster than the interpreted code; however, the compiled code takes up a lot more space than the executed code.
Whether this dynamically generated compiled code resides on the object heap or in a separate code cache region of memory, this compiled code is typically evicted from memory when it is no longer frequently accessed, and this eviction typically takes place through a garbage collection (GC) process. Note that the compiled code may contain pointers to objects which are handled by the GC process.
Although the actual eviction of the compiled code happens during GC, the victim selection portion of the eviction process is ideally based on information gathered during mutator execution, wherein the system can gather information to rank compiled methods according to how frequently they are used.
As memory constraints become tighter, the quality of this ranking process becomes increasingly more important to sustaining high overall execution speed. On the other hand, if the ranking mechanism becomes too complicated, obtaining ranking data may create a significant additional burden on the mutator.
In order to determine when a method is in use, it is a common practice to insert software hooks into specific locations in a method. These hooks can gather data and perform various computations when they are encountered during program execution.
Current victim selection schemes that use hooks fall into two categories, heavyweight hooks and lightweight hooks. With heavyweight hooks, the system performs some weighting calculation concerning a routine directly in the above hooks. For example, the hook can increment a counter in a Java method. In contrast, lightweight hooks produce a minimal amount of mutator slowdown by computing as little as possible in the hooks. For example, there is a self-modifying code scheme in the Connected Limited Device Configuration HotSpot Implementation (CLDC HI) within J2ME™ that patches the Java method callee prolog only the first time a hook is executed during a given GC cycle. In subsequent uses of the same routine, there is no mutator overhead.
Another way to determine method usage is to use statistical sampling. Statistical sampling operates by periodically analyzing the current stack to determine when routines are executing. (The statistical sampling method also counts as lightweight, since it typically executes relatively infrequently.)
However, all of the above-described techniques have drawbacks. They either slow down the mutator significantly, or they do not gather enough information for good victim selection. Furthermore, the interval between GCs is generally too large to establish a useful ranking among large numbers of methods. (Reflecting multiple GC intervals in multiple bits as in CLDC HI does not solve this problem, since one GC interval is generally already too long.)
Hence, what is needed is a method for determining a frequency of execution of compiled methods within a virtual machine without the drawbacks listed above.